package com.cwj.lab1;

import java.util.ArrayList;

/**
 * 双向链表实现数组
 * 之所以用双向链表主要是为了加快定位索引位置（方便删除和添加）；
 * 其中该线性表类实现了:添加元素（任意位置），删除元素，反转链表，查找的话
 */
public class LinkArray<T> {
    //链表节点
    public static class Node<T> {
        T data;//数据域，因为是泛型所以可以为任意类型
        Node<T> next;//后一个结点指针
        Node<T> pre;//前一个结点指针
        //构造器，可以简化下面实现的代码；
        public Node(T data, Node<T> next, Node<T> pre) {
            this.data = data;
            this.next = next;
            this.pre = pre;
        }
    }
    //双向链表的头节点head,和尾节点end
    //注意：此时head和end指向的都不是存储有效数据的节点，而是为了简化实现而始终的哨兵节点
    private final Node<T> head;
    private int len;//有效元素数量
    private final Node<T> end;

    //即在构造器中就要建好哨兵节点，哪怕空表即len=0,其两个节点也是存在的
    public LinkArray() {
        this.head = new Node<T>(null, null, null);
        this.end = new Node<T>(null, null, head);
        this.head.next = end;//让两个节点关联起来
        len = 0;
    }
  /**
   * @param data 在链表第一个位置新增一个节点，数据域为data;
   * */
    public void addFront(T data){
        this.head.next=new Node<T>(data,this.head.next,this.head);
        this.head.next.next.pre=this.head.next;
        len+=1;
//        上面实现也可为
//        this.insert(data,0);
    }
    /**
     * @param data 在链表最好位置新增一个节点，数据域为data;
     * */
    public void addLast(T data) {
        this.end.pre = new Node<T>(data, this.end, this.end.pre);
        this.end.pre.pre.next=this.end.pre;
        len += 1;
    }
/**
 * 插入节点
 * @param data 要插入结点的数据域
 * @param ind 要插入的位置
 * */
    public void insert(T data, int ind) {

        if(ind==this.len){
            this.addLast(data);
            return;
        }
        checkIndex(ind);
        //注意：我们实现的链表都是有哨兵结点的即头结点
        Node<T> flag = null;
        flag=this.getNode(ind);//定位原链表的ind位置的元素
        //下面为常见的结点插入逻辑，通过结点的构造器可以有效的简化代码
        flag.pre = new Node<T>(data, flag, flag.pre);
        flag.pre.pre.next=flag.pre;
        len += 1;
    }
    /**
     * 删除最后一个节点
     * */
    public void delLast() {
        //下面实现也可为,且因为是双向链表，所以效率一样
        //this.del(this.len-1);

        //检测链表是否为空,如果为空就会抛出异常
        checkEmpty();
        //因为是java，所以不需要释放内存，但如果为c++
        //否则就需要Node tt=end.pre;
        this.end.pre=this.end.pre.pre;
        this.end.pre.next=this.end;
        //delete tt;
        len-=1;
    }
    /**
     * 删除第一个元素
     * */
    public void delFront(){
        this.del(0);
    }
    /**
     * 删除指定位置的元素
     * 注意：ind的有效范围【0，len-1】;
     * @param ind 指定原数组的结点
     * @return 被删除元素的值
     * */
    public T del(int ind){
        Node<T> flag=this.getNode(ind);
        T data=flag.data;
        flag.pre.next=flag.next;
        flag.next.pre=flag.pre;
        flag.next=flag.pre=null;
        len-=1;
        return data;
    }
    /**
     * 获取第一个元素
     * 注意：其会检查链表是否为空，为空则抛出异常
     * */
    public T front(){
        checkEmpty();
        return head.next.data;
    }
    public T back(){
        checkEmpty();
        return end.pre.data;
    }
    /**
     * 有效元素数目
     * */
    public int size() {
        return len;
    }
    /**
     * 获取任意位置的结点的数据域
     * @param ind 指定位置
     * */
    public T get(int ind){
        checkIndex(ind);
        return getNode(ind).data;
    }
    /**
     * 打印这个数组，相当于变量一遍数组
     * */
    public void show(){
        Node<T> flag=head.next;
        System.out.print("{");
        while(flag!=this.end){
            System.out.print(flag.data+" ");
            flag=flag.next;
        }
        System.out.print("}");
        System.out.println("\tsize="+this.size());
    }
    /**
     * 数组是否为空
     * */
    public boolean isEmpty(){
        return len<=0;
    }
    /**根据索引位置获取结点
     * 得到索引为ind-1结点的引用，为什么是ind-1呢？因为这个结点的边界最简洁，
     * 而言想要找到正好为ind的结点，就下面的边界按注释提示改一下即可
     * @param ind 索引位置
     * @return 结点引用
     */
    private Node<T> getNode(int ind){
        Node<T> flag=null;
        if (ind <= len / 2) {
            flag=head;
            //ind-->ind+1
            for (int i = 0; i < ind+1; i++) {
                flag = flag.next;
            }
        }else{
            flag=end;
            //len-ind-->len-ind-1;
            for(int i=0;i<len-ind;i+=1){
                flag=flag.pre;
            }
        }
        return flag;
    }
    /**
     * 顺序查找
     * @param data 要查找的值
     * @return 如果存在就返回在线性表的索引位置，如果不在，就返回-1；
     * */
    public int find(T data){
        Node<T> flag=this.head.next;
        int ind=0;
        while(flag!=end){
            if(flag.data.equals(data)){
                return ind;
            }
            flag=flag.next;
        }
        return -1;
    }
    /**
     * 检查链表是否为空；仅仅用于访问线性表或是删除操作中，不对用户开放
     * */
    private void checkEmpty() {
        if (len <= 0) {
            throw new RuntimeException("数组为空");
        }
    }
    /**
     * 检查ind的合法值【0，len-1】
     * */
    private void checkIndex(int ind) {
        if (ind < 0 || ind >= len) {
            throw new RuntimeException("index越界");
        }
    }

    /**
     * 反转数组
     * 其思路为：从链表中删除一个元素，然后再利用头插法添加进链表中，从而实现链表反转
     * */
    public void reserve(){
        if(len<=0)return;
        Node<T> flag=this.head.next;
        Node<T> nn=null;
        while(flag!=end){
            nn=flag;
            flag=flag.next;
            nn.pre.next=nn.next;
            nn.next.pre=nn.pre;
            nn.next=head.next;
            nn.pre=head;
            head.next.pre=nn;
            head.next=nn;

        }

    }
    /**
     * 将线性表转化为字符串，遍历一遍
     * */
    @Override
    public String toString() {
        Node<T> flag=head.next;
        StringBuffer sb=new StringBuffer();
        while(flag!=this.end){
            sb.append(flag.data+" ");
            flag=flag.next;
        }
        return sb.toString();
    }

    //main函数负责进行数据结果的测试
    public static void main(String[] args) {
        LinkArray<Integer>list=new LinkArray<>();
        ArrayList<Integer> testList=new ArrayList<>();
        for (int i = 0; i < 30; i++) {
            if(choose(list,testList,(int)(Math.random()*20),(int)(Math.random()*4)))
                list.show();
        }
    }
    public static boolean choose(LinkArray<Integer>list,ArrayList<Integer>testList,int data,int ind){
        switch (ind){
            case 0:
                System.out.print("数组查找元素："+data+"-->结果：");
                System.out.print(list.find(data)+"\t-->");
                break;
            case 1:
                if(ind>=list.size()){
                    System.out.print("数尾插入元素："+data+"-->");
                    list.addLast(data);
                    break;
                }
                System.out.print("数组在"+ind+"索引处插入"+data+"-->");
                list.insert(data,(int)(Math.random()*list.size()-1));
                break;
            case 2:
                System.out.print("反转链表");
                list.reserve();
                break;
            case 3:
                if(ind>=list.size()){
                    return false;
                }
                System.out.print("数组删除"+ind+"索引处");
                System.out.print(list.get(ind)+"-->");
                list.del(ind);
                break;

        }
        return true;
    }

}
